PC Media 7/PC MEDIA CD07.iso/share/prog/cm/cmtbintr.cc

C/C++ Source or Header | 1994-09-06 | 10.6 KB | 416 lines

// CmTBinTr.cc
// -----------------------------------------------------------------
// Compendium - C++ Container Class Library
// Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
// -----------------------------------------------------------------
// Binary tree template implementation.
// -----------------------------------------------------------------


// "CmTBinaryTree" is the default tree constructor.
//
template <class T> CmTBinaryTree<T>::CmTBinaryTree()
                                   : _root(NULL)
{}


// "CmTBinaryTree" is the tree copy constructor.
//
template <class T> CmTBinaryTree<T>::CmTBinaryTree(const CmTBinaryTree<T>& tr)
                                   : CmTContainer<T>(tr)
{
  _root = NULL;
  copy   (tr);
  balance();
}


// "~CmTBinaryTree" is the tree destructor.
//
template <class T> CmTBinaryTree<T>::~CmTBinaryTree()
{
  removeAll();
}


// "=" assignment operator copies the specified tree into this tree.
//
template <class T>
CmTBinaryTree<T>& CmTBinaryTree<T>::operator=(const CmTBinaryTree<T>& tr)
{
  if (&tr != this)
  {
    removeAll();
    copy     (tr);
    balance  ();
  }
  return *this;
}


// "add" adds a new item to the tree.
//
template <class T> Bool CmTBinaryTree<T>::add(const T& rObj)
{
  CmTBinaryTreeNode<T> *newnode = new CmTBinaryTreeNode<T>(rObj);
  if (!newnode) return FALSE;

  if (!_root)                                // Tree is empty.  Add at root.
    _root = newnode;

  else                                       // Tree is not empty.
  {
    CmTBinaryTreeNode<T> *parent = _root;
    CmTBinaryTreeNode<T> *rover;
    rover = (rObj < _root->_data) ? _root->_left : _root->_right;

    while (rover)                            // Search for vacant slot.
    {
      parent = rover;
      rover  = (rObj < rover->_data) ? rover->_left : rover->_right;
    }

    if (rObj < parent->_data) parent->_left  = newnode;  // Add new node.
    else                      parent->_right = newnode;
  }
  _size++;
  return TRUE;
}


// "remove" removes the specified item from the tree.
//
template <class T> Bool CmTBinaryTree<T>::remove(const T& rObj)
{
  if (!_root) return FALSE;                    // Exit if empty tree.

  CmTBinaryTreeNode<T> *rover  = _root;        // Init for search.
  CmTBinaryTreeNode<T> *parent = NULL;
  Bool                  done   = FALSE;

  while (rover && !done)                       // Search for item.
  {
    if (rObj != rover->_data)                  // Advance to next node.
    {
      parent = rover;
      rover  = (rObj < rover->_data) ? rover->_left : rover->_right;
    }

    else                                       // Item was found.
    {
      CmTBinaryTreeNode<T> *temp1 = rover;     // Save pointer to object.

      if (rover->_right == NULL)
        rover = rover->_left;

      else if (rover->_right->_left == NULL)
      {
        rover        = rover->_right;
        rover->_left = temp1->_left;
      }

      else
      {
        CmTBinaryTreeNode<T> *temp2 = rover->_right;
        while (temp2->_left->_left) temp2 = temp2->_left;
        rover         = temp2->_left;
        temp2->_left  = rover->_right;
        rover->_left  = temp1->_left;
        rover->_right = temp1->_right;
      }

      if (!parent)                             // Object to remove is root.
        _root = rover;

      else
      {
        if (temp1->_data < parent->_data) parent->_left  = rover;
        else                              parent->_right = rover;
      }

      delete temp1;
      _size--;
      done = TRUE;
    }
  }
  return done;
}


// "lookup" returns the item in the tree equal to the specified item.
//
template <class T> const T& CmTBinaryTree<T>::lookup(const T& rObj) const
{
  if (!_root) return _error;

  CmTBinaryTreeNode<T> *rover = _root;
  CmTBinaryTreeNode<T> *temp  = NULL;

  while (rover && !temp)
  {
    if (rObj == rover->_data)
      temp  = rover;
    else
      rover = (rObj < rover->_data) ? rover->_left : rover->_right;
  }
  return (temp) ? temp->_data : _error;
}


// "contains" checks if the specified item is in this tree.
//
template <class T> Bool CmTBinaryTree<T>::contains(const T& rObj) const
{
  if (!_root) return NULL;

  CmTBinaryTreeNode<T> *rover = _root;
  Bool                  found = FALSE;

  while (rover && !found)
  {
    if (rObj == rover->_data)
      found = TRUE;
    else
      rover = (rObj < rover->_data) ? rover->_left : rover->_right;
  }
  return found;
}


// "removeAll" removes all items from this tree.
//
template <class T> void CmTBinaryTree<T>::removeAll()
{
  if (_root)
  {
    killNode(_root);
    delete _root;
    _root = NULL;
    _size = 0;
  }
}


// "occurrences" counts the occurrences of the specified item in this tree.
//
template <class T> unsigned CmTBinaryTree<T>::occurrences(const T& rObj) const
{
  unsigned                 occur = 0;
  CmTBinaryTreeIterator<T> iterator(*this);
  while (!iterator.done())
    if (iterator.next() == rObj) occur++;
  return occur;
}


// "root" returns the item at the root of this tree.
//
template <class T> const T& CmTBinaryTree<T>::root() const
{
  return (_root) ? _root->_data : _error;
}


// "balance" balances the current contents of the tree.
//
template <class T> void CmTBinaryTree<T>::balance()
{
  CmTQueue<CmTBinaryTreeNode<T>*> *que = new CmTQueue<CmTBinaryTreeNode<T>*>;
  CmTBinaryTreeIterator<T> iterator(*this);
  while (!iterator.done())
  {
    CmTBinaryTreeNode<T> *newnode = new CmTBinaryTreeNode<T>(iterator.next());
    if (newnode) que->push(newnode);
  }
  removeAll();
  balanceHalf(que, 0, que->size() - 1);
  delete que;
}


// "newIterator" creates and returns a new tree iterator.
//
template <class T> CmTIterator<T>* CmTBinaryTree<T>::newIterator() const
{
  return new CmTBinaryTreeIterator<T>(*this);
}


// "balanceHalf" is called recursively for tree balancing.
//
template <class T>
void CmTBinaryTree<T>::balanceHalf(CmTQueue<CmTBinaryTreeNode<T>*> *que,
                                   int low, int high)
{
  if (low <= high)
  {
    int mid = (low + high) / 2;
    add(((*que)[mid])->_data);
    balanceHalf(que, mid + 1, high);
    balanceHalf(que, low, mid-1);
  }
}


// "killNode" is recursively called to destroy branches of a node.
//
template <class T> void CmTBinaryTree<T>::killNode(CmTBinaryTreeNode<T>* sub)
{
  if (sub->_left)
  {
    killNode(sub->_left);
    delete sub->_left;
    sub->_left = NULL;
  }

  if (sub->_right)
  {
    killNode(sub->_right);
    delete sub->_right;
    sub->_right = NULL;
  }
}


// "CmTBinaryTreeIterator" is the iterator constructor.
//
template <class T>
CmTBinaryTreeIterator<T>::CmTBinaryTreeIterator(const CmTBinaryTree<T>& tr)
                                                : _tree(tr)
{
  _stack = new CmTStack<CmTBinaryTreeNode<T>*>;
  _node  = _tree._root;
  if (_node)
  {
    while (_node->_left)
    {
      _stack->push(_node);
      _node = _node->_left;
    }
  }
}


// "~CmTBinaryTreeIterator" is the iterator destructor.
//
template <class T> CmTBinaryTreeIterator<T>::~CmTBinaryTreeIterator()
{
  delete _stack;
}


// "done" returns TRUE if the iterator can proceed no further.
//
template <class T> Bool CmTBinaryTreeIterator<T>::done() const
{
  return (!_node);
}


// "next" returns the current item and advances the iterator.
//
template <class T> const T& CmTBinaryTreeIterator<T>::next()
{
  if (!_node) return _tree._error;                // Iteration is over.

  const T& retValue = _node->_data;               // Save item reference.

  if (_node->_right)                              // If there is a right
  {                                               // branch, advance to it
    _stack->push(_node);                          // and descend all the way
    _node = _node->_right;                        // down it's left side.
    while (_node->_left)
    {
      _stack->push(_node);
      _node = _node->_left;
    }
  }

  else                                            // Otherwise, back up the
  {                                               // tree until we are back
    CmTBinaryTreeNode<T>* temp;                   // at the top or until we
    do                                            // are no longer a right
    {                                             // branch.
      temp  = _node;
      if (_stack->size() == 0) _node = NULL;
      else                     _node = _stack->pop();
    } while (_node && _node->_right == temp);
  }
  return retValue;
}


// "previous" returns the current item and advances the iterator.
//
template <class T> const T& CmTBinaryTreeIterator<T>::previous()
{
  if (!_node) return _tree._error;                // Iteration is over.

  const T& retValue = _node->_data;               // Save item reference.

  if (_node->_left)                               // If there is a left
  {                                               // branch, advance to it
    _stack->push(_node);                          // and descend all the way
    _node = _node->_left;                         // down it's right side.
    while (_node->_right)
    {
      _stack->push(_node);
      _node = _node->_right;
    }
  }

  else                                            // Otherwise, back up the
  {                                               // tree until we are back
    CmTBinaryTreeNode<T>* temp;                   // at the top or until we
    do                                            // are no longer a left
    {                                             // branch.
      temp  = _node;
      if (_stack->size() == 0) _node = NULL;
      else                     _node = _stack->pop();
    } while (_node && _node->_left == temp);
  }
  return retValue;
}


// "current" returns the curren item.
//
template <class T> const T& CmTBinaryTreeIterator<T>::current() const
{
  return (_node) ? _node->_data : _tree._error;
}


// "first" moves the iterator to the first item.
//
template <class T> void CmTBinaryTreeIterator<T>::first()
{
  _stack->removeAll();
  _node = _tree._root;
  if (_node)
  {
    while (_node->_left)
    {
      _stack->push(_node);
      _node = _node->_left;
    }
  }
}


// "last" moves the iterator to the last item.
//
template <class T> void CmTBinaryTreeIterator<T>::last()
{
  _stack->removeAll();
  _node = _tree._root;
  if (_node)
  {
    while (_node->_right)
    {
      _stack->push(_node);
      _node = _node->_right;
    }
  }
}